排序 | Hikari

1 排序的基本概念

1.1 排序的定义

排序：重新排列表中元素，使表中元素满足按关键字递增或递减的过程
算法的稳定性：关键字相同的不同元素排序前后前后相对顺序不变，称该算法是稳定的
内部排序：排序期间元素全存放在内存的排序
外部排序：排序期间元素需要在内外存之间移动的排序

2 插入排序

2.1 直接插入排序

排序思想：序列分为有序部分和无序部分，每次排序将无序部分的一个元素加入有序部分进行排序，重复上述步骤直到全部排序完成。

void InsertSort(Elemtype A[],int n){
    int i,j;
    for(i=2;i<=n;i++){            //依次将A[2]到A[n]插入到已排序序列
        A[0]=A[i];              //A[0]为哨兵
        for(j=i-1;A[j].key>A[i].key&&;j--)   //若前驱元素大于A[i】，将其后移一位
            A[j+1]=A[j];
        A[j+1]==A[0];                 //插入A[i]
    }
}

算法时间复杂度：O(n²);
算法空间复杂度：O(1)；
稳定性：稳定

2.2 折半插入排序

算法思想：利用折半查找在有序序列中查找目标元素的插入位置，再一次性移动元素后插入目标元素。

void InsertSort(Elemtype A[],int n){
    it i,j,low,mid,high;
    for(i=2;i<=n;i++){              //依次将A[2]到A[n]插入到已排序序列
        A[0]=A[i];                  //A[0]存储待排序元素
        low=1;
        high=i-1;
        while(low<=high){           //查找插入位置
            mid=(low+high)/2;
            if(A[mid].key>A[0].key)
                high=mid-1;
            else low=mid+1;
        }
        for(j=i-1;j>-high+1;j--)    //移动元素
            A[j+1]=A[j];

        A[high+1]=A[0]              //插入元素
    }
    //为什么插入位置是A[high+1]
    //可以这样理解：【特例】当源序列有序时，元素插入位置为原来位置，即A[high+1]
}

2.3 希尔排序

算法思想：直接插入排序中，排序元素取的步长为1，即比较时是A[i]和A[i+1]进行比较；而希尔排序中取得步长为di(di取值：1= < di <=(n/2)),每一轮排序后将步长减小，直到di=1这一轮排序完成则全部排序完成。

void ShellSort(Elemtype A[],int n){
    int di=n/2;
    for(di;di>=1;di=di/2){              //每轮排序后步长减半
        int i;
        for(i=di+1;i<=n;i++){          //从A[i+di]开始进行直接插入排序
            A[0]=A[i];
            if(A[i]<A[i-di]){          //判断已排序的最后元素大于欲排序元素，再排序，否则不予排序
                int j;
                for(j=i-di;j>0;j--){    //后移
                    A[j+di]=A[j];
                }
                A[j+di]=A[0];          //插入
            }
        }
    }
}

最坏时间复杂度：O(n²);
稳定性：不稳定

3 交换排序

根据序列中两个元素关键字的比较结果决定是否交换两个元素的位置的排序称为交换排序

3.1 冒泡排序

void BubbleSort(Elemtype A[],int n){
    for(int i=0;i<n-1;i++){             //从小到大排序
        bool flag=false;                //本轮排序是否交换的标志位
        for(int j=n-1;j>i;j--){         //从尾部开始检测是否交换
            if(A[j-1]>A[j])
                swap(A[j-1],A[j]);
                flag=true;
        }
        if(flag==false)             //若本轮未发生交换，说明排序已完成，直接返回
            return;
    }
}

时间复杂度：O(n²)
稳定性：由于A[i]=A[j]时不会发送交换，所以为稳定排序。

3.2 快速排序

算法思想：取待排序列中一元素pivot作为基准，经过一趟快速排序确定pivot的最终位置，并划分出大于等于pivot的部分和小于等于pivot的部分；再对每个子序列重复上述过程，直到每一部分只含一个或0个元素，则排序完成。
一趟快速排序

int Partition(Elemtype A[],int low,int high){
    Elemtype pivot = A[low];
    while(low<hight){
        while(low<high&&A[high]>pivot)
            high--;
        A[low]=A[high];
        while(low<high&&A[low]<pivot)
            low++;
        A[high]=A[low];
    }
    A[low]=pivot;
    return low;
}

快排

void QuickSOrt(Elemtype A[],int low,int high){
    if(low<high){
        int partition=Partition(A,low,high);
        QuickSOrt(A,low,partition-1);
        QuickSOrt(A,partition+1,high);
    }
}

空间复杂度：快排算法为递归算法，需要借助递归工作栈；其空间复杂度为栈的深度，其平均值为O(log₂n)。
时间复杂度：O(n²)

4 选择排序

选择排序算法思想：每趟排序选择未排序元素中关键字最小的元素，将其加入到已排序序列的末尾。

4.1 简单选择排序

void SelectSort(Elemtype A[],int n){
    for(int i=0;i<n-1;i++){
        min=i;
        for(int j=i+1;j<=n-1;j++){
            if(min>A[j]) min=j;
        }
        if(A[min]!=A[i]) swap(A[min],A[i]); 
    }
}

时间复杂度：O(n²)
稳定性：交换元素期间会打乱原来含有相同关键字的元素的顺序，不稳定。

4.2 堆排序

堆排序是一种树形选择排序方式，序列L[1]到L[n]经过堆排序后的结构符合完全二叉树的顺序存储结构。
其严格定义为：n个关键字序列L[1…n]称为堆，当且仅当：
1.L[i]<=L[2i] && L[i]<=L[2i+1] (小顶堆) 或
2.L[i]>=L[2i] && L[i]>=L[2i+1] （大顶堆）。
堆排序算法思想：

对待排序序列生成器层序遍历树。
从结点⌊n/2⌋ 开始，若左右子结点的最大值大于根结点，将根结点与之交换，再对该根结点以下的子结点进行递归操作。

对结点序号小于⌊n/2⌋的结点从大到小依次进行步骤1和2的操作，直到第一个结点也完成上述操作。
建堆算法：

void BuildMaxHeap(Elemtype A[],int len){
    for(int i=len/2;i>0;i--)
        AdjustDown(A,i,len);
}
void AdjustDown(Elemtype A[],int k ,int len){
    if(k<=len/2){           //
        A[0]=A[k];//将父结点存储在A[0]中，注意原序列序号是从1开始，0序号元素不存储元素信息，故可以对其进行再次利用
        for(int i=2*k;i<=len;i*=2){ //i代表子结点下标
            if(i<len&&A[i]<A[i+1])  //选出子结点中值比较大的的结点
                i=i+1;
            if(A[k]>A[i]) break;  //如果子结点值比父节点小，则说明该趟排序完成
            else{
                A[k]=A[i];       //用子结点代替父结点
                k=i；            //修改k值，继续向子结点进行操作
            }
        }
        A[k]=A[0];              //父结点的最终存放位置
    }
}

堆排序算法：

void HeapSort(Elemtype A[],int len){
    BuildMaxHeap;       //建大顶堆
    for(int i=len;i>1;i--){     //从大到小进行len-1趟排序
        Swap(A[len,A[1]]);      //交换堆顶元素和堆顶元素
        AdjustDown(A,1,i-1)   //对剩余元素进行调整使其成堆
    }
}

堆排序算法性能：
空间复杂度：O(1)
时间复杂度：O(nlog₂n)
稳定性：不稳定

5 归并排序和基数排序

5.1 归并排序

归并排序是将两个或者两个以上的有序序列合并为一个新的有序表

Elemtype *B=(Elemtype *)malloc(sizeof(Elemtype)*(n+1))
void Merge(Elemtype A[],int low,int mid,int high){
    //表A[low...mid]和A[mid+1...high]分别有序，将它们合并为一个表
    for(int i=low;i<=high;i++){         //将A复制给B
        B[i]=A[i];
    }
    int i,j;
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){ //将两分表中值小的复制到A中，下标后移
        if(B[i]<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];       //加入剩余元素
    while(j<=high) A[k++]=B[j++];
}

void MergeSort(Elemtype A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1;high);
        Merge(A,low,mid,high);
    }
    //递归边界为low=high，此时将不进行操作
}

时间复杂度：O(nlog₂n)
稳定性：稳定

5.2 基数排序

　　基数排序是基于关键字各位的大小进行排序的，基数排序分为最高位（MASD）优先和排序和最低位优先(LSD)排序。
　　排序步骤（以LSD为例）：第一趟排序时只考虑最低位，第二趟排序时只考虑次低位，以此进行n轮排序直到首位也完成排序则基数排序完成。在每趟排序时不进行比较，而是将其放入到已知的容器中，之后再将元素直接按照所在容器的顺序首尾相连，得到一趟排序的结果。，
　　时间复杂度：每趟排序时有n个元素要进行入队列（队列数目为r）的操作，之后需要连接这r个队列，操作次数为(n+r);设元素共有d位，则需要进行d趟排序，故时间复杂度为O(d*(n+r))。
　　空间复杂度：需要r个队列，故为O(r)。

6 各种内部排序算法的比较

算法	最好时间复杂度	平局时间复杂度	最坏时间复杂度	空间复杂度	稳定性
直接插入排序	O(n)	O(n² )	O(n²)	O(1)	是
希尔排序				O(1)	否
简单选择排序	O(n² )	O(n² )	O(n² )	O(1)	否
冒泡排序	O(n)	O(n² )	O(n² )	O(1)	是
快速排序	O(nlog₂n)	O(n²)	O(n²)	O(log₂n)	否
堆排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(1)	否
2-路归并排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(n)	是
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	是